1. FIELD OF THE INVENTION
The present invention relates to the field of computer systems. More specifically, the present invention relates to the art of caching decoded micro-operations with trace segments and providing a victim cache for replaced cache lines.
2. DESCRIPTION OF RELATED ART
Historically, cached instructions are stored and organized in an instruction cache in accordance with the instructions' memory addresses. Each cache line stores a number of instructions that are spatially adjacent each other in main memory. This historic approach to caching instructions has at least one disadvantage in that it typically requires multiple cache lines to be accessed when execution of a program necessitates branching from the middle of a cache line or branching into the middle of a cache line.
In a cache organized by instruction address, a full line of adjacent instructions is typically fetched from the main memory and loaded into the cache. If the cache becomes fill, an existing line in the cache memory is replaced to accommodate a new line of instructions required by the microprocessor. The replacement of a particular line does not impact any other lines in the cache.
An alternative approach to organizing cached instructions is known, whereby cached instructions are organized by instruction trace segments. Each cache line stores an instruction trace segment comprising one or more basic blocks of instructions that are predicted to be sequentially executed. For example, in an embodiment where each cache line comprises two basic blocks of instructions, the second basic block of instructions includes instructions to be executed if the branch instruction located at the end of the first basic block is taken. Assuming the branch is predicted taken, the second basic block is included in the same trace segment. A particular trace segment may extend over a number of cache lines. Each trace segment is retrieved based on the memory address of the first instruction in the trace segment.
A cache organized by trace segments is typically operated in one of two modes, an execution mode, and a build mode. Instructions are read from the cache memory during the execution mode and trace segments are built into the cache memory in the build mode. If an instruction required by the microprocessor is not present in the cache memory, a cache miss is generated and the cache memory switches to build mode. A switch to build mode results in a performance penalty due to the latency generated as new instructions must be fetched, decoded, and supplied to the microprocessor.
In a trace cache arrangement, a line replacement is more costly than in a traditional cache arrangement. For example, consider a trace segment occupying six cache lines. The fourth line of the trace segment is replaced. Because the trace segment can only be accessed through the address of the first instruction in the first cache line (i.e. the head of the trace segment), only lines one, two, and three, will be accessible after the replacement of the fourth line. Lines, five and six will be unavailable because they were cut off from the trace segment when the fourth line was replaced.
As a result, when the processor accesses the trace segment to retrieve instructions, a cache miss will occur after the third line. The processor will then switch to build mode to begin a new trace segment including the replaced fourth line and cut off fifth and sixth lines. As a result, the instructions contained in the fifth and sixth lines will be cached twice.
Thus, it is desirable to have a new approach for caching instructions that reduces the performance penalty caused by cache line replacements and reduces the degree of code redundancy present in the cache.